from math import fabs, log
from random import uniform
import logging

class Recurrencer:
    @classmethod
    def get_root(cls, d1, d2):
        if (d1 == d2):
            return 2**(1 / d1)
        
        t = min(d1, d2)
        d1 = max(d1, d2)
        d2 = t

        def f(x):
            return x**(d1) - x**(d1 - d2) - 1

        # f' = d1 * x^(d1 - 1) - (d1 - d2) * x^(d1 - d2 - 1)
        # f' = x^(d1 - d2 - 1) * ( d1 * x^(d2) - (d1 - d2) )
        # f' == 0 <==> (x == 0) or ( ( d1 * x^(d2) - (d1 - d2) ) == 0 )
        # f' == 0 <==> (x == 0) or ( ( x^(d2) == (d1 - d2) / d1 )
        # f' == 0 <==> (x == 0) or ( d2 * ln(x) == ln(1 - (d2 / d1) ) )
        # f' == 0 <==> (x == 0) or ( x == e^(ln(1 - (d2 / d1) ) / d2 ) )
        
        x0 = 2**(log(1 - (d2 / d1), 2) / d2)
        x1 = max(x0, 1.0)

        logging.debug('d1 = %f, d2 = %f, x0 = %f, x1 = %f' % (d1, d2, x0, x1))

        while (f(x1) < 0):
            x0 = x1
            x1 *= 2

        _max_error = 10**-6
        _max_root = 1.5

        while (x1 - x0 > _max_error):
            assert (x1 - x0 > 0)

            x = (x1 + x0) / 2
            if (f(x) > 0):
                x1 = x
            else:
                x0 = x

            if x0 > _max_root:
                return _max_root

        root = (x1 + x0) / 2

        return root

    @classmethod
    def add_elements(cls, set_size, num_elements):
        def add_element(buckets):
            if len(buckets) == 1:
                return [[buckets[0] + 1]]

            l = [buckets[0] + 1] + list(buckets[1:])

            r = [l]

            for l in add_element(buckets[1:]):
                t = [buckets[0]] + l
                r.append(t)

            return r

        l = []
        for _ in range(num_elements):
            l.append(0)

        all_buckets = set([tuple(l)])

        for _ in range(set_size):
            l = []
            for b in all_buckets:
                l.extend(map(tuple, add_element(b)))
            all_buckets = set(l)

        return all_buckets


class ParamsSeeker:
    @classmethod
    def rand_params(cls, seed, params_range):
        ret = []
        last = 0
        for i in seed:
            ret.append(uniform(max(last, i - params_range),
                               min(i + params_range, 1)))
            last = ret[-1]
        return tuple(ret)

    
# from cProfile import run
# run('print seek_best_params(7)')
